package com.zhugang.week05;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @program algorithms
 * @description: relativeSortArray
 * @author: chanzhugang
 * @create: 2022/07/11 15:01
 */
public class RelativeSortArray2 {

    public static void main(String[] args) {
        RelativeSortArray2 relativeSortArray = new RelativeSortArray2();
        int[] arr1 = new int[]{28, 6, 22, 8, 44, 17};
        int[] arr2 = new int[]{22, 28, 8, 6};
        int[] res = relativeSortArray.relativeSortArray(arr1, arr2);
        for (int num : res) {
            System.out.println(num);
        }
    }

    /**
     * 1122 数组的相对排序
     *
     * @param arr1
     * @param arr2
     * @return
     */
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        // arr1 相对顺序和 arr2相对顺序相同， arr1中剩余的按升序排
        // arr2的元素在arr1中出现的次数、先按arr2中顺序排，剩余的升序排
        Map<Integer, Integer> mapCounts = new HashMap<>();
        for (int num : arr2) {
            mapCounts.put(num, 0);
        }
        for (int num : arr1) {
            if (mapCounts.containsKey(num)) {
                mapCounts.put(num, mapCounts.get(num) + 1);
            }
        }

        int[] resArr = new int[arr1.length];
        int k = 0;
        for (int i = 0; i < arr2.length; i++) {
            Integer count = mapCounts.get(arr2[i]);
            for (int j = 0; j < count; j++) {
                resArr[k + j] = arr2[i];
            }
            k += count;
        }

        Arrays.sort(arr1);
        for (int i = 0; i < arr1.length; i++) {
            if (!mapCounts.containsKey(arr1[i])) {
                resArr[k++] = arr1[i];
            }
        }
        return resArr;
    }
}
